package arithmetic.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 链表数据结构算法
 *
 */
public class ListTest {


    /**
     * LeetCode -2
     * 两数相加
     * 给你两个非空的链表，表示两个非负的整数；它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
     * ***和两个整数字符串相加逻辑一样
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
        int carry = 0;//代码进位数
        ListNode p,dummy = new ListNode(0);
        p = dummy;
        while (l1 != null || l2 != null || carry != 0){
            if (l1 != null){
                carry += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                carry += l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(carry % 10);
            carry = carry/10;
            p = p.next;
        }
        return dummy.next;
    }


    /**
     * 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists1(ListNode list1, ListNode list2){
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        ListNode listNode = new ListNode(0);
        ListNode p=listNode;
        while (list1 != null & list2 != null){
            if(list1.val<list2.val){
                p.next=list1;
                list1=list1.next;
            }else {
                p.next=list2;
                list2=list2.next;
            }
            p=p.next;
        }
        if(list1!=null){
            p.next=list1;
        }
        if(list2!=null){
            p.next=list2;
        }
        return listNode.next;
    }

    /**
     * LeetCode - 23 合并K个升序链表
     * 给你一个链表数组,每个链表都已经按升序排列
     * 请你将所有链表合并到一个升序链表中,返回合并后的链表
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     *
     * 分二治之;最后用合并两个有序列表的思想
     */
    public ListNode mergeLists(ListNode[] lists){
        return merge(lists,0,lists.length -1);
    }
    public ListNode merge(ListNode[] lists, int left, int right) {
         if(left == right){
             return lists[left];
         }
         if (left > right){
             return null;
         }
         int mid = (left + right) >> 1;
         return mergeTwoLists1(merge(lists, left, mid), merge(lists,mid+1, right));
    }

    /**
     * 每日温度:
     * 请根据每日气温列表temp,请计算在每一天需要等几天才会有个更高的温度。
     * 如果气温在这之后都不会升高，请在该位置用0代替。
     *
     * 输入：temp =[73,74,75,71,69,72,76,73];
     * 输出：[1,1,4,2,1,1,0,0]
     *
     * 1、栈的解法
     *  peek()--不删除栈的值
     *  pop()--会把栈顶的值删除掉
     *
     * 2、利用倒序遍历进行求解
     */
    //标准栈的解法
    public static int[] dailyTemp(int[] temp){
        Deque<Integer> stack = new LinkedList<Integer>();
        int[] ret = new int[temp.length];
        for (int i =0; i < temp.length; i++){
            while (!stack.isEmpty() && temp[i] > temp[stack.peek()]){
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }

    /**
     * 链表中倒数第k个节点
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
     * 还可以使用双指针
     */
    /**
     * 双指针
     * 1、2、3、4、5、6 倒数第K个节点，就是让快指针先执行k-1个节点
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd1(ListNode head, int k){
        ListNode fast=head;
        ListNode slow=head;
        int i=0;
        while (fast!=null){
            fast=fast.next;
            if(i==k-1){
                break;
            }
            i++;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    /**
     * @author zhangzg
     * 回文链表:
     * 偶数节点个数-- 1->2->3->3->2->1
     * 奇数节点个数-- 1->2->3->2->1
     *
     * 使用双节点+反转列表
     *
     * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     * @date 2022/11/1
     */
    /**
     * 快慢指针双节
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head){
        ListNode fast=head,slow=head;
        while (fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //链表是奇数节点个数
        if(fast!=null){
            slow=slow.next;
        }
        //慢指针的剩余链表进行反转链表操作
        slow=reverse(slow);
        //快指针还原
        fast=head;
        while (slow!=null){
            if(slow.val!= fast.val){
                return false;
            }
            slow=slow.next;
            fast=fast.next;
        }
        return true;
    }
    private static ListNode reverse(ListNode head) {
        ListNode preNode=null;
        ListNode curNode=head;
        while (curNode!=null){
            ListNode next=curNode.next;
            curNode.next=preNode;
            preNode=curNode;
            curNode=next;
        }
        return preNode;
    }

    /**
     * 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     */
    public static ListNode reverseList(ListNode head){
        ListNode preNode=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode next=cur.next;
            cur.next=preNode;
            preNode=cur;
            cur=next;
        }
        return preNode;
    }
    //递归
    public static ListNode reverseList1(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode newHead=reverseList1(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }

    //


}


class ListNode{
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int x){
        val=x;
        next=null;
    }
}